package array.leetcode.medium;

import java.util.HashMap;
import java.util.Map;

/**
 * @author bruin_du
 * @description 0 和 1 个数相同的子数组
 * @date 2022/8/4 14:53
 **/
public class OfferII011_FindMaxLength {
    //前缀和加哈希表
    public int findMaxLength(int[] nums) {
        int res = 0, len = nums.length, sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) sum--;
            else sum++;
            if (map.containsKey(sum)) {
                res = Math.max(res, i - map.get(sum));
            }else{
                map.put(sum, i);
            }
        }
        return res;
    }
}
